package com.leetcode;


/**
 * 1250. 检查「好数组」 (困难)
 * 给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
 * 假如该和结果为1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
 */
public class LeetCode1250 {

    public static void main(String[] arg0) {
        int[] test = {12,5,7,23};
        System.out.println("是否是「好数组」 = " + isGoodArray(test));
    }

    /**
     * 「裴蜀定理」
     * 任意多个数的最大公约数为a，那个这些一定存在这些数各自乘以某个整数之后相加等于a。
     * 所以这题只要能从数组取出子集的数的最大公约数是1，就返回TRUE，也就是整个数组的最大公约数是1即可。
     */
    public static boolean isGoodArray(int[] nums) {
        if (nums.length == 1) {
            if (nums[0] == 1) {
                return true;
            } else {
                return false;
            }
        }

        int currGcd = gcd(nums[0], nums[1]);
        if (currGcd == 1) {
            return true;
        }
        for (int i = 2; i < nums.length; i++) {
            currGcd = gcd(nums[i], currGcd);
            if (currGcd == 1) {
                return true;
            }
        }
        return false;
    }

    public static int gcd(int a, int b) {
        return a < b ? gcd(b, a) : (a % b == 0) ? b : gcd(b, a % b);
    }

}
